package madixin.t42;

import java.util.Stack;

class Solution {
    //单调栈
    public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int distance = i - stack.peek() - 1;
                int bounded_height = Math.min(height[i], height[stack.peek()]) - height[top];
                res += distance * bounded_height;
            }
            stack.push(i);
        }
        return res;
    }

    //双指针法
    public int trap1(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;//左右最高的夹板
        int rightMax = 0;
        int res = 0;
        while (left <= right) {
            if (leftMax <= rightMax) {
                if (height[left] < leftMax) {
                    res += leftMax - height[left];
                }
                leftMax = Math.max(leftMax, height[left]);
                left++;
            } else {
                if (height[right] < rightMax) {
                    res += rightMax - height[right];
                }
                rightMax = Math.max(rightMax, height[right]);
                right--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }
}
